package top.minuy.structure.graph.path.weighted;

import top.minuy.res.graph.GraphRes;
import top.minuy.structure.graph.representations.table.WeightedGraph;

import java.util.Random;

/**
 * 带权图最短路径生成算法
 *
 * @author Minuy
 * @time 20:04
 * @date 2021/11/25
 */
public class Test {
    public static void main(String[] args) {
        Random random = new Random();

        System.out.println("Dijkstra 算法：");
        System.out.println("0 : ");
        testDij(0);
        System.out.println("4 : ");
        testDij(4);

        System.out.println("Dijkstra 路径测试：");
        WeightedGraph g = new WeightedGraph(GraphRes.G_DIJKSTRA_1);
        DijkstraPQPath dpp = new DijkstraPQPath(g, 0);
        for (int i = 1; i < g.V(); i++) {
            int t = random.nextInt(g.V());
            System.out.println(String.format("%d -> %d : ", 0, t) + dpp.path(t));
        }


        System.out.println("BellmanFord 算法：");
        testBFM(GraphRes.G_BELLMAN_FORD_01, 0);
        testBFM(GraphRes.G_BELLMAN_FORD_02, 1);


        System.out.println("BellmanFord 路径测试：");
        WeightedGraph gb = new WeightedGraph(GraphRes.G_BELLMAN_FORD_01);
        BellmanFordPath bmp = new BellmanFordPath(gb, 0);
        for (int i = 1; i < gb.V(); i++) {
            int t = random.nextInt(gb.V());
            System.out.println(String.format("%d -> %d : ", 0, t) + bmp.path(t));
        }


        System.out.println("Floyed 算法：");
        testFLD(GraphRes.G_FLOYED_01);
        testFLD(GraphRes.G_FLOYED_02);

        System.out.println("有向图测试：");
        WeightedGraph wg = new WeightedGraph(GraphRes.G_DIRECTED_02, true);
        System.out.println("Floyed 算法：");
        fld(wg);
        System.out.println("BellmanFord 算法：");
        bfm(wg, 0);
    }

    /**
     * 测试Floyed算法
     *
     * @param path 输入路径
     * @author Minuy
     * @date 2021/11/26 20:50
     */
    private static void testFLD(String path) {
        WeightedGraph gf = new WeightedGraph(path);
        fld(gf);
    }

    private static void fld(WeightedGraph gf) {
        Floyed floyed = new Floyed(gf);
        if (!floyed.hasNegativeCycle()) {
            for (int v = 0; v < gf.V(); v++) {
                System.out.print(v + " : ");
                for (int w = 0; w < gf.V(); w++) {
                    System.out.print((" {->" + w + ":" + floyed.disTo(v, w) + "}").replace("2147483647", "∞"));
                    if (w != gf.V() - 1) {
                        System.out.print(',');
                    } else {
                        System.out.println();
                    }
                }
            }
        } else {
            System.out.println("Graph has negative cycle.");
        }
    }

    private static void testBFM(String path, int s) {
        WeightedGraph g = new WeightedGraph(path);
        bfm(g, s);

    }

    private static void bfm(WeightedGraph g, int s) {
        System.out.println("-> Bellman-Ford 默认实现：");
        BellmanFord bmf = new BellmanFord(g, s);
        if (!bmf.hasNegativeCycle()) {
            for (int v = 0; v < g.V(); v++) {
                System.out.println(String.format("%d->%d : %d", s, v, bmf.disTo(v)).replace("2147483647", "∞"));
            }
        } else {
            System.out.println("Graph has Negative Cycle!");
        }
    }

    private static void testDij(int s) {
        WeightedGraph g = new WeightedGraph(GraphRes.G_DIJKSTRA_1);

        System.out.println("-> Dijkstra 默认实现：");
        Dijkstra dijkstra = new Dijkstra(g, s);
        for (int v = 0; v < g.V(); v++) {
            System.out.println(String.format("%d->%d : %d", s, v, dijkstra.disTo(v)).replace("2147483647", "∞"));
        }

        System.out.println("-> Dijkstra 优化实现：");
        DijkstraPQ dpq = new DijkstraPQ(g, s);
        for (int v = 0; v < g.V(); v++) {
            System.out.println(String.format("%d->%d : %d", s, v, dpq.disTo(v)).replace("2147483647", "∞"));
        }
    }


}
